#include <stdio.h>
#include <string.h>
const int SIZE =1000010;
char text[SIZE];
const int PSIZE = 10010;
char par[PSIZE];
int next [PSIZE];
void findnext();
int kmp();
int main()
{
    freopen("dat.in","r",stdin);
    freopen("dat.out","w",stdout);
    int cas=0;
    scanf("%d",&cas);
    while (cas--)
    {
          scanf("%s",par);
          scanf("%s",text);
          findnext();
          int ans = kmp();
          printf("%d\n",ans);
    }
    //while (1);
    return 0;
}
void findnext()
{
     int len = strlen(par);
     int i=0,j=-1;
     next[0]=-1;
     for (i=1;i<len;i++){
         while (j>0 && par[j+1]!=par[i]){
             j=next[j];
         }
         if (par[j+1]==par[i]){
             j++;
         }
         next[i]=j;
     }
}
int kmp()
{
    int cnt=0;
    int i=0,j=-1;
    int tlen=strlen(text);
    int plen=strlen(par);

    for (i=0;i<tlen;i++){
        while (j>=0 && par[j+1]!=text[i]){
            j=next[j];
        }
        if (par[j+1]==text[i]){
            j++;
        }
        if (j+1==plen){
            cnt++;
        }
    }

/* this is also ok
    while (i<tlen){
        while(j+1<plen && i<tlen && par[j+1]==text[i]){
            j++;
            i++;
        }
        if (j+1==plen){
            cnt++;
        }
        if (j==-1){
            while ( i<tlen && par[j+1]!=text[i]){
                i++;
            }
        }else{
            j=next[j];
        }
    }
    */
    return cnt;
}
